package com.leecode.exercise;

/**
 * @Author: shubin_yao
 * @Date: 2022/04/03/16:13
 * @Description: 回文字符串
 * <p>
 * 中心扩散法
 */
public class StringPalindrome {
    public static void main(String[] args) {
        //String s = "babad";
        String s = "ac";
        StringPalindrome palindrome = new StringPalindrome();
        String s1 = palindrome.longestPalindrome(s);

        System.out.println(s1);
    }


    public String longestPalindrome(String s) {
        int len = 0;
        int start = 0;
        if (s == null || s == "" || s.length() == 0) {
            return s;
        }

        //奇数
        // i 中心点 ，j 扩张次数
        if (s.length() % 2 == 1) {
            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; i - j >= 0 && i + j < s.length(); j++) {
                    if (s.charAt(i - j) == s.charAt(i + j)) {
                        int tempLen = 2 * j + 1;
                        if (tempLen > len) {
                            start = i - j;
                            len = tempLen;
                        }
                    } else {
                        break;
                    }
                }
            }
        }

        //偶数
        if (s.length() % 2 == 0) {
            for (int i = 0; i + 1 < s.length(); i++) {
                for (int j = 0; i - j >= 0 && i + 1 + j < s.length(); j++) {
                    if (s.charAt(i - j) == s.charAt(i + 1 + j)) {
                        int tempLen = 2 * j + 2;
                        if (tempLen > len) {
                            start = i - j;
                            len = tempLen;
                        }
                    } else {
                        break;
                    }
                }
            }
        }
        return s.substring(start, start + len);
    }

}

